package org.example.dfs;

import java.util.*;

/**
 * @author liyishan
 * @date 2023/8/31 13:18
 * @apiNote
 */

public class Test00047PermuteUnique {

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        dfs(nums,used,res,list);
        return res;
    }

    public static void dfs(int[] nums,boolean[] used,List<List<Integer>> res ,List<Integer> list){
        if(list.size() == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0;i < nums.length;i++){
            if(i>0 && nums[i] == nums[i-1] && used[i-1] == false){
                continue;
            }
            if(!used[i]){
                used[i] = true;
                list.add(nums[i]);
                dfs(nums,used,res,list);
                list.remove(list.size()-1);
                used[i] = false;
            }
        }
    }

}
